home *** CD-ROM | disk | FTP | other *** search
/ GFX Sensations 1 / Graphic Sensations - Volume 1.iso / tools / amiga / 3d_tools / irit40s.lha / Irit / poly3d-h / prepdata.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-30  |  27.0 KB  |  766 lines
  1. /*****************************************************************************
  2. *   Routines to    prepare objects according to view file matrix:             *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 1.0, Jan. 1989   *
  5. *****************************************************************************/
  6.  
  7. #include <math.h>
  8. #include <stdio.h>
  9. #include "program.h"
  10. #include "genmat.h"
  11.  
  12. /* #define DEBUG1                  Print edge/hash table content. */
  13.  
  14. #define SAME_VERTEX(V1, V2)    (APX_EQ(V1 -> Coord[0], V2 -> Coord[0]) && \
  15.                  APX_EQ(V1 -> Coord[1], V2 -> Coord[1]) && \
  16.                  APX_EQ(V1 -> Coord[2], V2 -> Coord[2]))
  17.  
  18. #ifdef DEBUG1
  19. static void PrintEdgeContent(EdgeStruct *PEdge);
  20. static void DrawEdgeHashTable(void);
  21. static void DrawEdge(EdgeStruct *PEdge);
  22. #endif /* DEBUG1 */
  23.  
  24. static int MinYLevel, MaxYLevel, CrntYLevel, PrintYLevel;
  25.  
  26. static void PrepareAllObjects(IPObjectStruct *PObjects);
  27. static void PrepareOneObject(IPObjectStruct *PObject);
  28. static int PrepareOnePolygon(IPPolygonStruct *PPolygon, int IsPolygon);
  29. static void UpdateBBoxPolygon(IPPolygonStruct *PPolygon);
  30. static int UpdateEqnPolygon(IPPolygonStruct *PPolygon, int *ReversePoly);
  31. static IPVertexStruct *ReverseLinList(IPVertexStruct *VList);
  32. static void GenEdgesFromPoly(IPPolygonStruct *PPolygon, int IsPolygon);
  33. static void InsertEdgeToHashTbl1(EdgeStruct *PEdge);
  34. static void IntersectAllEdges(void);
  35. static void InsertEdgeToHashTbl2(EdgeStruct *PEdge);
  36. static int IntersectEdgeList(EdgeStruct *PEdge, EdgeStruct *PEList,
  37.                                 int TestYMin);
  38. static int IntersectEdgeEdge(EdgeStruct *PEdge1, EdgeStruct *PEdge2,
  39.             EdgeStruct **PEdgeNew1, EdgeStruct **PEdgeNew2);
  40. static void PrintPolyContent(IPPolygonStruct *PPoly);
  41.  
  42. /*****************************************************************************
  43. * Routine to prepare to draw NumOfObjects given in Objects from             *
  44. * FileDescription FD according to view matrix Mat. If NumOfObjects == 0    then *
  45. * all the objects defined by the data sturcture    are drawn.             *
  46. * If GlblNumEdge != 0 then only GlblNumEdge first edges of each polygons are *
  47. * tested for visibility    (usefull in case in input polygons has known         *
  48. * repitition edges sequence which is redundent).                 *
  49. *****************************************************************************/
  50. void PrepareViewData(IPObjectStruct *PObjects)
  51. {
  52.     int    i;
  53.  
  54.     IritCPUTime(TRUE);
  55.  
  56.     for    (i = 0; i < EDGE_HASH_TABLE_SIZE; i++)
  57.     EdgeHashTable[i] = NULL;
  58.     for    (i = 0; i < POLY_HASH_TABLE_SIZE; i++)
  59.     PolyHashTable[i] = NULL;
  60.  
  61.     if (!GlblQuiet)
  62.     fprintf(stderr, "\nPass 2, Edges =      ");
  63.  
  64.     PrepareAllObjects(PObjects);
  65.  
  66.     if (!GlblQuiet)
  67.     fprintf(stderr, ",  %6.2lf seconds.", IritCPUTime(FALSE));
  68.  
  69.     IntersectAllEdges();       /* Break edges to visibily uniform sub-edges. */
  70. }
  71.  
  72. /*****************************************************************************
  73. * Scan all objects.                                 *
  74. *****************************************************************************/
  75. static void PrepareAllObjects(IPObjectStruct *PObjects)
  76. {
  77.     while (PObjects) {
  78.     if (IP_IS_POLY_OBJ(PObjects))
  79.         PrepareOneObject(PObjects);
  80.     PObjects = PObjects -> Pnext;
  81.     }
  82. }
  83.  
  84. /*****************************************************************************
  85. * Routine to prepare one object PObject.                     *
  86. *****************************************************************************/
  87. static void PrepareOneObject(IPObjectStruct *PObject)
  88. {
  89.     int Level;
  90.     IPPolygonStruct *Ptemp,
  91.     *PList = PObject -> U.Pl;
  92.  
  93.     while (PList) {
  94.     Ptemp = PList -> Pnext;
  95.  
  96.     if (!IritPrsrIsConvexPolygon(PList)) {
  97.         static int Printed = FALSE;
  98.  
  99.         if (!Printed) {
  100.         fprintf(stderr,
  101.             "\nWARNING: Non convex polygon(s) might be in data (see CONVEX in IRIT),\n\t\t\t\toutput can be wrong as the result!\n     ");
  102.         Printed = TRUE;
  103.         }
  104.     }
  105.  
  106.     if (PrepareOnePolygon(PList, IP_IS_POLYGON_OBJ(PObject))) {
  107.         /* And add polygon into polygon hash table sorted by Ymin: */
  108.         Level = (int) ((PList -> BBox[0][1] + 1.0) * POLY_HASH_TABLE_SIZE2);
  109.         Level = BOUND(Level, 0, POLY_HASH_TABLE_SIZE1); /* Be 100% safe. */
  110.         PList -> Pnext = PolyHashTable[Level];
  111.         PolyHashTable[Level] = PList;   /* Concat it to poly hash table. */
  112.     }
  113.  
  114.     PList =    Ptemp;
  115.     }
  116. }
  117.  
  118. /*****************************************************************************
  119. * Routine to prepare one polygon PPolygon.                     *
  120. * Returns TRUE iff this object is a valid POLYGON (not a POLYLINE!).         *
  121. *****************************************************************************/
  122. static int PrepareOnePolygon(IPPolygonStruct *PPolygon, int IsPolygon)
  123. {
  124.     int    i, Reverse;
  125.     RealType CpCoord[3];
  126.     IPVertexStruct
  127.     *PList = PPolygon -> PVertex;
  128.  
  129.     /* Make a circluar polygon list inlt a linear list by breaking the end.  */
  130.     while (PList != NULL && PList -> Pnext != PPolygon -> PVertex)
  131.     PList = PList -> Pnext;
  132.     if (PList)
  133.     PList -> Pnext = NULL;
  134.     PList = PPolygon -> PVertex;
  135.  
  136.     while (PList) {
  137.     /* Convert the coordinate to screen space (in RealType pres.). */
  138.     MatMultVecby4by4(CpCoord, PList -> Coord, GlblViewMat);
  139.     for (i = 0; i < 3; i++)
  140.         PList -> Coord[i] = CpCoord[i];
  141.  
  142.     PList =    PList -> Pnext;
  143.     }
  144.     if (IsPolygon) {
  145.     /* Find plane equation of poly, and let know if need to reverse. */
  146.     if (!UpdateEqnPolygon(PPolygon, &Reverse))
  147.         return FALSE;
  148.     UpdateBBoxPolygon(PPolygon);/* Find X, Y extrem in screen space. */
  149.     GenEdgesFromPoly(PPolygon, TRUE);      /* Generate all its edges. */
  150.     if (Reverse)
  151.             PPolygon -> PVertex = ReverseLinList(PPolygon -> PVertex);
  152.     return TRUE;
  153.     }
  154.     else {
  155.     GenEdgesFromPoly(PPolygon, FALSE);      /* Generate all its edges. */
  156.     return FALSE;
  157.     }
  158. }
  159.  
  160. /*****************************************************************************
  161. * Routine to update polygon boundary box in screen space:             *
  162. * Note this routine is called after the    polygons was checked for validity -  *
  163. * all the list of objects was found to be vertices only.             *
  164. *****************************************************************************/
  165. static void UpdateBBoxPolygon(IPPolygonStruct *PPolygon)
  166. {
  167.     RealType *Coord, Xmin, Xmax, Ymin, Ymax; /* Bounding box of the polygon. */
  168.     IPVertexStruct
  169.     *PList = PPolygon -> PVertex;
  170.  
  171.     Xmin = Xmax    = PList -> Coord[0];
  172.     Ymin = Ymax    = PList    -> Coord[1];
  173.     PList = PList -> Pnext;
  174.     while (PList) {
  175.     Coord = PList -> Coord;
  176.     if (Coord[0] > Xmax)
  177.         Xmax = Coord[0];
  178.     if (Coord[0] < Xmin)
  179.         Xmin = Coord[0];
  180.     if (Coord[1] > Ymax)
  181.         Ymax = Coord[1];
  182.     if (Coord[1] < Ymin)
  183.         Ymin = Coord[1];
  184.     PList =    PList -> Pnext;
  185.     }
  186.     PPolygon ->    BBox[0][0] = Xmin;
  187.     PPolygon -> BBox[1][0] = Xmax;
  188.     PPolygon ->    BBox[0][1] = Ymin;
  189.     PPolygon -> BBox[1][1] = Ymax;
  190. }
  191.  
  192. /*****************************************************************************
  193. * Routine to update plane equation of the given    polygon:             *
  194. *   It is assumed that at list 3 points in polygon do exists, and pick the   *
  195. * tuple that has biggest length for maximum accuracy.                 *
  196. *   Note we IGNORE PLANE if was in data file.                     *
  197. *   In addition a test is made if all polygon vertices are ordered such that *
  198. * the cross product of each 3 consecutive vertices (projected to Z=0 plane)  *
  199. * is allways positive. Note the    polygon    must be    convex,    so result might    be   *
  200. * all positive or all negative.    In the later case the order is reversed         *
  201. *****************************************************************************/
  202. static int UpdateEqnPolygon(IPPolygonStruct *PPolygon, int *ReversePoly)
  203. {
  204.     static int
  205.     PolygonCount = 0;
  206.     int    i;
  207.     RealType V1[3], V2[3], *Coord, *CoordNext, *CoordNextNext,
  208.     Plane[3], Len, MaxPlane[3],
  209.     MaxLen = 0.0;
  210.     IPVertexStruct
  211.     *PList = PPolygon -> PVertex;
  212.  
  213.     PolygonCount++;
  214.  
  215.     *ReversePoly = FALSE;
  216.  
  217.     do {    /* Search for 3 consequtive non-colinear point from polygon: */
  218.     Coord = PList -> Coord;
  219.     CoordNext = PList -> Pnext -> Coord;
  220.     CoordNextNext = PList -> Pnext -> Pnext -> Coord;
  221.     for (i = 0; i < 3; i++) {   /* Prepare two vectors on polygon plane. */
  222.         V1[i] = Coord[i] - CoordNext[i];
  223.         V2[i] = CoordNext[i] - CoordNextNext[i];
  224.     }
  225.  
  226.     /* Find plane normal by a cross product of the two vectors on plane: */
  227.     Plane[0] = V1[1] * V2[2] - V1[2] * V2[1];
  228.     Plane[1] = V1[2] * V2[0] - V1[0] * V2[2];
  229.     Plane[2] = V1[0] * V2[1] - V1[1] * V2[0];
  230.  
  231.     /* Find vector Len. - we are looking for the biggest: */
  232.     Len = sqrt(SQR(Plane[0]) + SQR(Plane[1]) + SQR(Plane[2]));
  233.     if (Len > MaxLen) {
  234.         for (i = 0; i < 3; i++)
  235.         MaxPlane[i] = Plane[i];
  236.         MaxLen = Len;
  237.     }
  238.     PList = PList -> Pnext;                  /* Try next tuple. */
  239.     } while (PList -> Pnext -> Pnext != NULL);
  240.  
  241.     if (ABS(MaxLen) < SQR(EPSILON)) { /* Fail to find 3 non-colinear points. */
  242.     if (GlblMore) {
  243.         fprintf(stderr,
  244.             "\nError: Invalid polygon (%d) found in file (zero edge length/colinear vertices):\n",
  245.         PolygonCount);
  246.         PrintPolyContent(PPolygon);
  247.     }
  248.     return FALSE;
  249.     }
  250.  
  251.     for (i = 0; i < 3; i++)
  252.     PPolygon -> Plane[i] = MaxPlane[i] / MaxLen;
  253.  
  254.     /* Make sure the Z component of the    plane is positive: */
  255.     if (PPolygon -> Plane[2] < 0.0) {
  256.     for (i = 0; i < 3; i++)
  257.         PPolygon -> Plane[i] = (-PPolygon -> Plane[i]);
  258.     *ReversePoly = TRUE;
  259.     }
  260.     else
  261.         if (GlblBackFacing)
  262.         return FALSE;
  263.  
  264.     PPolygon ->    Plane[3] =
  265.     (- Coord[0] * PPolygon -> Plane[0]
  266.      - Coord[1] * PPolygon -> Plane[1]
  267.      - Coord[2] * PPolygon -> Plane[2]);
  268.  
  269.     return TRUE;
  270. }
  271.  
  272. /*****************************************************************************
  273. * Routine to evaluate the cross    product    of 3 points projected to Z = 0 plane *
  274. * and return the sign of the result (Only Z component).                 *
  275. *****************************************************************************/
  276. int CrossProd(RealType Pt1[3], RealType Pt2[3], RealType Pt3[3])
  277. {
  278.     RealType Zout;
  279.  
  280.     /* U = Pt2 - Pt1,  V = Pt3 - Pt2,        Zoutput    = Ux * Vy - Uy * Vx. */
  281.     Zout = (Pt2[0] - Pt1[0]) /*    Ux */  * (Pt3[1] - Pt2[1]) /* Vy */  -
  282.        (Pt2[1] - Pt1[1]) /*    Uy */  * (Pt3[0] - Pt2[0]) /* Vx */;
  283.     if (APX_EQ(Zout, 0.0))
  284.     return 0;
  285.     if (Zout < 0.0)
  286.     return -1;
  287.     else
  288.     return 1;
  289. }
  290.  
  291. /*****************************************************************************
  292. * Routine to reverse linear list PList - return    pointer    to the reversed    list *
  293. * Although this routine is basically generic, it should be called on the     *
  294. * VertexStruct only as it updates their Internal flags as well.             *
  295. *****************************************************************************/
  296. static IPVertexStruct *ReverseLinList(IPVertexStruct *VList)
  297. {
  298.     int i;
  299.     IPVertexStruct *VLtemp,
  300.     *VLreverse = NULL;
  301.  
  302.     while (VList != NULL) {
  303.     VLtemp = VList -> Pnext;/* Save pointer to next element in old list. */
  304.  
  305.     VList -> Pnext = VLreverse; /* Add old element in front of new list. */
  306.     VLreverse = VList;
  307.  
  308.     VList =    VLtemp;            /* Continue to next element in old list. */
  309.     }
  310.  
  311.     VLtemp = VLreverse;
  312.     i = VLtemp -> Tags;
  313.     while (VLtemp != NULL) {
  314.     if (VLtemp -> Pnext != NULL) {
  315.         VLtemp -> Tags = VLtemp -> Pnext -> Tags;
  316.     }
  317.     else {
  318.         VLtemp -> Tags = i;
  319.     }
  320.  
  321.     VLtemp = VLtemp -> Pnext;
  322.     }
  323.  
  324.     return VLreverse;
  325. }
  326.  
  327. /*****************************************************************************
  328. * Routine to generate all the edges from the given polygon in screen space.  *
  329. * The polygon must be valid - only vertices in its list.             *
  330. * Edges    are inserted to    an edge    hash table of EDGE_HASH_TABLE_SIZE entries.  *
  331. * If global variable GlblNumEdge != 0 then only the first PGlblNumEdge edges *
  332. * are generated.                                 *
  333. * If edge is INTERNAL it is marked as so.                     *
  334. * If this is polyline, the last edge is NOT generated.                 *
  335. *****************************************************************************/
  336. static void GenEdgesFromPoly(IPPolygonStruct *PPolygon, int IsPolygon)
  337. {
  338.     int    CountEdges = GlblNumEdge;
  339.     EdgeStruct *PEdge;
  340.     IPVertexStruct
  341.     *PList = PPolygon -> PVertex;
  342.  
  343.     if (!PList || !PList -> Pnext)
  344.     return;                     /* If less than 2 vertices. */
  345.  
  346.     while (PList -> Pnext) {
  347.     PEdge =    (EdgeStruct *) IritMalloc(sizeof(EdgeStruct));
  348.     PEdge -> Vertex[0] = PList;
  349.     PEdge -> Vertex[1] = PList -> Pnext;
  350.     PEdge -> Internal = IP_IS_INTERNAL_VRTX(PList);
  351.     PEdge -> Pnext = NULL;
  352.     InsertEdgeToHashTbl1(PEdge);
  353.  
  354.     if (!--CountEdges)
  355.         return;
  356.  
  357.     PList =    PList -> Pnext;
  358.     }
  359.     /* Close the contour to first vertex in list (if not polyline): */
  360.     if (IsPolygon) {
  361.     PEdge = (EdgeStruct *) IritMalloc(sizeof(EdgeStruct));
  362.     PEdge -> Vertex[0] = PList;
  363.     PEdge -> Vertex[1] = PPolygon -> PVertex;
  364.     PEdge -> Internal = IP_IS_INTERNAL_VRTX(PList);
  365.     PEdge -> Pnext = NULL;
  366.     InsertEdgeToHashTbl1(PEdge);
  367.     }
  368. }
  369.  
  370. /*****************************************************************************
  371. * Routine to insert new    edge to    edge hash table    structure sorted (hashed) by *
  372. * the edge Y min value.    The edge is tested for duplicated entry    (if         *
  373. * interior edge    - entered twice    and ignored in this case.             *
  374. * Also the edge    is updated such    that Ymin will be Vertex[0], Ymax Vertex[1]. *
  375. *****************************************************************************/
  376. static void InsertEdgeToHashTbl1(EdgeStruct *PEdge)
  377. {
  378.     int    Level;
  379.     RealType Xmin, Xmax, Ymin, Ymax;
  380.     IPVertexStruct *PVertex;
  381.     EdgeStruct *PEtemp;
  382.  
  383.     if (PEdge -> Vertex[0] -> Coord[1] > PEdge -> Vertex[1] -> Coord[1]) {
  384.     PVertex    = PEdge    -> Vertex[0];
  385.     PEdge -> Vertex[0] = PEdge -> Vertex[1];
  386.     PEdge -> Vertex[1] = PVertex;
  387.     }
  388.     Xmin = MIN(PEdge -> Vertex[0] -> Coord[0],
  389.            PEdge -> Vertex[1] -> Coord[0]);
  390.     Xmax = MAX(PEdge -> Vertex[0] -> Coord[0],
  391.            PEdge -> Vertex[1] -> Coord[0]);
  392.     Ymin = PEdge -> Vertex[0] -> Coord[1];
  393.     Ymax = PEdge -> Vertex[1] -> Coord[1];
  394.  
  395.     if (GlblClipScreen && ((Ymin > 1.0) || (Ymax < -1.0) ||
  396.                (Xmin > 1.0) || (Xmax < -1.0)))
  397.     IritFree((VoidPtr) PEdge);               /* Out of screen. */
  398.     else {
  399.     /* Normalize [-1..1] to    [0..EDGE_HASH_TABLE_SIZE]: */
  400.     Level =    (int) ((Ymin + 1.0) * EDGE_HASH_TABLE_SIZE2);
  401.     Level =    BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1);     /* To be 100% safe. */
  402.  
  403.     /* Look    for duplicate entry - it must have the same two    vertices: */
  404.     PEtemp = EdgeHashTable[Level];
  405.     while (PEtemp) {
  406.         /* Test to see if same edge    by comparing vertices pointers.    */
  407.         if ((SAME_VERTEX(PEdge -> Vertex[0], PEtemp -> Vertex[0]) &&
  408.          SAME_VERTEX(PEdge -> Vertex[1], PEtemp -> Vertex[1])) ||
  409.         (SAME_VERTEX(PEdge -> Vertex[0], PEtemp -> Vertex[1]) &&
  410.          SAME_VERTEX(PEdge -> Vertex[1], PEtemp -> Vertex[0]))) {
  411.         IritFree((VoidPtr) PEdge);
  412.         return;                    /* Ignore new entry! */
  413.         }
  414.         PEtemp = PEtemp -> Pnext;
  415.     }
  416.  
  417.     if (!GlblQuiet)
  418.         fprintf(stderr, "\b\b\b\b\b%5d", ++EdgeCount);
  419.     PEdge -> Pnext = EdgeHashTable[Level];         /* Concat to main list. */
  420.     EdgeHashTable[Level] = PEdge;
  421.     }
  422. }
  423.  
  424. /*****************************************************************************
  425. * Routine to collect all edges in hash table into one big list and intersect *
  426. * them among themselves. In any    intersection both edges    are broken into    two. *
  427. * The resulting    edges are inserted back    into the hash table:             *
  428. *****************************************************************************/
  429. static void IntersectAllEdges(void)
  430. {
  431.     RealType Ymin;
  432.     int    i, Level;
  433.     EdgeStruct *PEmain = NULL, *PEtemp;
  434.  
  435.     IritCPUTime(TRUE);
  436.  
  437.     EdgeCount =    0;
  438.     MinYLevel =    EDGE_HASH_TABLE_SIZE; /* Set "clip" levels in table entries. */
  439.     MaxYLevel =    0;
  440.  
  441.     /* Clear the hash table and    collect    all edges into one big list: */
  442.     for    (i = EDGE_HASH_TABLE_SIZE1; i >= 0; i--)
  443.     if ((PEtemp = EdgeHashTable[i]) != NULL) {
  444.         while (PEtemp -> Pnext) PEtemp = PEtemp -> Pnext;
  445.         PEtemp -> Pnext = PEmain;
  446.         PEmain = EdgeHashTable[i];
  447.         EdgeHashTable[i] = NULL;
  448.         if (i > MaxYLevel)
  449.         MaxYLevel = i;
  450.         if (i < MinYLevel)
  451.         MinYLevel = i;
  452.     }
  453.  
  454.     PrintYLevel    = CrntYLevel = 0;     /* Have to start from some place... */
  455.     if (!GlblQuiet)
  456.     fprintf(stderr, "\nPass 3, Level [%5d] =      ", MaxYLevel);
  457.  
  458.     while (PEmain) { /* Insert back after intersecting with all other edges. */
  459.     PEtemp = PEmain    -> Pnext;      /* As PEmain->Pnext might be changed. */
  460.     InsertEdgeToHashTbl2(PEmain);
  461.     PEmain = PEtemp;
  462.  
  463.     /* Now test to see if we can update current y level: */
  464.     if (CrntYLevel < MaxYLevel) {
  465.         Ymin = MIN(PEmain -> Vertex[0] -> Coord[1],
  466.                PEmain -> Vertex[1] -> Coord[1]);
  467.         /* Normalize [-1..1] to [0..EDGE_HASH_TABLE_SIZE]: */
  468.         Level = (int) ((Ymin + 1.0) * EDGE_HASH_TABLE_SIZE2);
  469.         Level = BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1); /* Be 100% safe. */
  470.         if (Level > CrntYLevel)
  471.         CrntYLevel = Level;
  472.     }
  473.     }
  474.     if (!GlblQuiet)
  475.     fprintf(stderr, ",  %6.2lf seconds.", IritCPUTime(FALSE));
  476. }
  477.  
  478. /*****************************************************************************
  479. * Routine to insert old    edge to    edge hash table    structure sorted (hashed) by *
  480. * the edge Y min value.    The edge is tested for intersections with other         *
  481. * edges    allready in structure and both edges are broken    if found one.         *
  482. *****************************************************************************/
  483. static void InsertEdgeToHashTbl2(EdgeStruct *PEdge)
  484. {
  485.     int    i, Level, UpperLevel,
  486.     FoundIntersection = FALSE;
  487.     RealType Ymin, Ymax;
  488.     EdgeStruct *PEtemp;
  489.  
  490.     Ymin = PEdge -> Vertex[0] -> Coord[1];
  491.     Ymax = PEdge -> Vertex[1] -> Coord[1];
  492.  
  493.     /* Normalize [-1..1] to [0..EDGE_HASH_TABLE_SIZE]: */
  494.     Level = (int) ((Ymin + 1.0)    * EDGE_HASH_TABLE_SIZE2);
  495.     Level = BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1);      /* To be 100% safe. */
  496.     UpperLevel = 1 + (int) ((Ymax + 1.0) * EDGE_HASH_TABLE_SIZE2);
  497.     UpperLevel = BOUND(UpperLevel, 0, EDGE_HASH_TABLE_SIZE1);
  498.  
  499.     if (CrntYLevel > PrintYLevel) {
  500.     PrintYLevel = CrntYLevel;
  501.     if (!GlblQuiet)
  502.         fprintf(stderr, "\b\b\b\b\b%5d", PrintYLevel);
  503.     }
  504.  
  505.     /* Test for    intersections while we find intersections... */
  506.     for    (i=MinYLevel; i<=UpperLevel; i++)
  507.     if (EdgeHashTable[i])
  508.          if ((FoundIntersection =
  509.           IntersectEdgeList(PEdge, EdgeHashTable[i],
  510.                     i == MinYLevel)) != 0)
  511.         break;
  512.  
  513.     if (FoundIntersection) {       /* Call recursively with the edge pieces: */
  514.     while (PEdge) {
  515.         PEtemp = PEdge -> Pnext;  /* As Pedge->Pnext might point to new. */
  516.         InsertEdgeToHashTbl2(PEdge);   /* Place after the recursive ins. */
  517.         PEdge = PEtemp;
  518.     }
  519.     }
  520.     else {              /* Its a single edge - insert it in its place: */
  521.     EdgeCount++;
  522.     PEdge -> Pnext = EdgeHashTable[Level];         /* Concat to main list. */
  523.     EdgeHashTable[Level] = PEdge;
  524.     }
  525. }
  526.  
  527. /*****************************************************************************
  528. * Routine to scan all edges in list and    intersect everything against         *
  529. * the given edge. intersected edges are    broken into two    parts each. The    edge *
  530. * is updated to    a list of 2 pieces, and    the list edge is broken    and inserted *
  531. * to the hash table (one piece in same entry as    it has the same    Ymin).         *
  532. * Note this routine returns TRUE after the first intersection found - no     *
  533. * test is made for ALL intersections if    more than one exists.             *
  534. * A test is made if MinYLevel can be updated if    TestYMin == TRUE.         *
  535. *****************************************************************************/
  536. static int IntersectEdgeList(EdgeStruct *PEdge, EdgeStruct *PEList,
  537.                                 int TestYMin)
  538. {
  539.     int    Level,
  540.     UpdateYMin = TRUE;
  541.     RealType Ymin, Ymax;
  542.     EdgeStruct *PEdgeNew, *PEListNew;
  543.  
  544.     if (!PEdge || !PEList)
  545.     return FALSE;                       /* NULL entry - quit. */
  546.  
  547.     while (PEList) {
  548.     if (IntersectEdgeEdge(PEdge, PEList, &PEdgeNew,    &PEListNew)) {
  549.         PEdge -> Pnext = PEdgeNew;
  550.         /* PEListNew can be    inserted to the    hash table with    no check as  */
  551.         /* its cannt intersect anything - it is part of checked edge!    */
  552.         if (PEListNew) {
  553.         Ymin = PEListNew -> Vertex[0] -> Coord[1];
  554.         /* Normalize [-1..1] to    [0..EDGE_HASH_TABLE_SIZE]: */
  555.         Level =    (int) ((Ymin + 1.0) * EDGE_HASH_TABLE_SIZE2);
  556.         Level =    BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1);
  557.         EdgeCount++;
  558.         PEListNew -> Pnext = EdgeHashTable[Level];
  559.         EdgeHashTable[Level] = PEListNew;
  560.         }
  561.         return TRUE;
  562.     }
  563.     if (TestYMin &&    UpdateYMin) {
  564.         Ymax = PEList -> Vertex[1] -> Coord[1];
  565.         /* Normalize [-1..1] to [0..EDGE_HASH_TABLE_SIZE]: */
  566.         Level = (int) ((Ymax + 1.0)    * EDGE_HASH_TABLE_SIZE2);
  567.         Level = BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1);
  568.         if (Level >= CrntYLevel)
  569.         UpdateYMin = FALSE;
  570.     }
  571.     PEList = PEList    -> Pnext;
  572.     }
  573.     if (TestYMin && UpdateYMin)            /* No need to test any more. */
  574.     do
  575.         MinYLevel++;
  576.     while (MinYLevel < CrntYLevel && !EdgeHashTable[MinYLevel]);
  577.  
  578.     return FALSE;
  579. }
  580.  
  581. /*****************************************************************************
  582. * Routine to test if two edges intersects. If they do, it brakes the bottom  *
  583. * edge into two pieces, leaving the lower part (with the same Ymin) in         *
  584. * original struct and allocated and updates new struct with upper edge part. *
  585. * Returns TRUE if found intersection, FALSE otherwise.                 *
  586. * Note the intersection    is tested in the XY axes (Z is ignored!).         *
  587. *****************************************************************************/
  588. static int IntersectEdgeEdge(EdgeStruct *PEdge1, EdgeStruct *PEdge2,
  589.                  EdgeStruct **PEdgeNew1, EdgeStruct **PEdgeNew2)
  590. {
  591.     int    i, OneInter1, OneInter2;
  592.     RealType Xmin1, Xmax1, Ymin1, Ymax1, Xmin2, Xmax2, Ymin2, Ymax2,
  593.       a1, b11, b12, a2, b21, b22, det, t1, t2, Z1, Z2;
  594.     /* To speed    up the intensive access    of the coordinates: */
  595.     RealType
  596.     *Crd10 = PEdge1 -> Vertex[0] -> Coord,
  597.     *Crd11 = PEdge1 -> Vertex[1] -> Coord,
  598.     *Crd20 = PEdge2 -> Vertex[0] -> Coord,
  599.     *Crd21 = PEdge2 -> Vertex[1] -> Coord;
  600.  
  601.     Xmin1 = MIN(Crd10[0], Crd11[0]);
  602.     Xmax1 = MAX(Crd10[0], Crd11[0]);
  603.     Ymin1 = Crd10[1];
  604.     Ymax1 = Crd11[1];
  605.  
  606.     Xmin2 = MIN(Crd20[0], Crd21[0]);
  607.     Xmax2 = MAX(Crd20[0], Crd21[0]);
  608.     Ymin2 = Crd20[1];
  609.     Ymax2 = Crd21[1];
  610.     if ((Xmin1 > Xmax2)    || (Xmax1 < Xmin2) ||/* Test if out of Boundary Box. */
  611.     (Ymin1 > Ymax2)    || (Ymax1 < Ymin2))
  612.     return FALSE;
  613.  
  614.     /* Let the line equations of the two edges be defined as:             */
  615.     /* L1 = p11    + t1 * (pt12 - pt11) , t1 = [0..1]                 */
  616.     /* L2 = p21    + t2 * (pt22 - pt21) , t2 = [0..1]                 */
  617.     /* at intersection point (if any) we have:                     */
  618.     /* pt11 + t1 * (pt12 - pt11) == pt21 + t2 *    (pt22 -    pt21)  for x, y         */
  619.     /* or two equations    (for x, y) with two unknown (t1, t2) to solve:         */
  620.     /* a1 = b11    * t1 + b12 * t2        from x                     */
  621.     /* a2 = b21    * t1 + b22 * t2        from y                     */
  622.     /* and we have interesection if both t1, t2    in the range [0..1]         */
  623.     a1 =  Crd10[0] - Crd20[0];
  624.     b11    = Crd10[0] - Crd11[0];
  625.     b12    = Crd21[0] - Crd20[0];
  626.     a2 =  Crd10[1] - Crd20[1];
  627.     b21    = Crd10[1] - Crd11[1];
  628.     b22    = Crd21[1] - Crd20[1];
  629.  
  630.     /* If the detereminant is zero, the    two lines are parellel - no inter. */
  631.     if (APX_EQ((det = b11 * b22 - b21 * b12), 0.0))
  632.     return FALSE;
  633.  
  634.     t1 = (a1 * b22 - a2    * b12) / det;
  635.     t2 = (b11 *    a2 - b21 * a1) / det;
  636.  
  637.     /* Test if intersection is happening in one    edge END - in that case    */
  638.     /* we break    only the second    edge into two parts.            */
  639.     OneInter1 =    ((t1 < 1.0) && (t1 > 0.0) &&
  640.          !(APX_EQ(t1, 0.0) || APX_EQ(t1, 1.0)) &&
  641.           (APX_EQ(t2, 0.0) || APX_EQ(t2, 1.0)));
  642.     OneInter2 =    ((t2 < 1.0) && (t2 > 0.0) &&
  643.          !(APX_EQ(t2, 0.0) || APX_EQ(t2, 1.0)) &&
  644.           (APX_EQ(t1, 0.0) || APX_EQ(t1, 1.0)));
  645.  
  646.     /* If out of 0..1 range in one of edges - no intersection: */
  647.     if ((!(OneInter1 ||    OneInter2)) &&
  648.     ((t1 >=    1.0) ||    (t1 <= 0.0) || (t2 >= 1.0) || (t2 <= 0.0) ||
  649.      APX_EQ(t1, 0.0) || APX_EQ(t1, 1.0) ||
  650.      APX_EQ(t2, 0.0) || APX_EQ(t2, 1.0))) return FALSE;
  651.  
  652.     /* If we are here, we have intersection - find the bottom edge and split */
  653.     /* it - allocated new edge struct and update to new upper (in Y) part.   */
  654.     Z1 = Crd10[2] * (1.0 - t1) + Crd11[2] * t1;
  655.     Z2 = Crd20[2] * (1.0 - t2) + Crd21[2] * t2;
  656.     if (!OneInter2 && Z1 < Z2) {
  657.     *PEdgeNew1 = (EdgeStruct *) IritMalloc(sizeof(EdgeStruct));
  658.     (*PEdgeNew1) -> Pnext = NULL;
  659.     (*PEdgeNew1) -> Internal = PEdge1 -> Internal;
  660.     (*PEdgeNew1) ->    Vertex[0] = IPAllocVertex(0, 0, NULL, NULL);
  661.     for (i = 0; i < 2; i++)
  662.         (*PEdgeNew1) -> Vertex[0] -> Coord[i] =
  663.         Crd10[i] * (1.0    - t1) +    Crd11[i] * t1;
  664.     (*PEdgeNew1) -> Vertex[0] -> Coord[2] = Z1;
  665.     /* Now update the second vertex    of both    PEdge1 & PEdgeNew1:       */
  666.     /* Note    we assume Vertex[0] -> Coord[1]    < Vertex[1] -> Coord[1]    as */
  667.     /* all input edges are sorted this way when entered to hash table. */
  668.     (*PEdgeNew1) ->    Vertex[1] = PEdge1 -> Vertex[1];
  669.     PEdge1 -> Vertex[1] = (*PEdgeNew1) -> Vertex[0];
  670.  
  671.     }
  672.     else
  673.     *PEdgeNew1 = NULL;
  674.  
  675.     if (!OneInter1 && Z2 < Z1) {
  676.     *PEdgeNew2 = (EdgeStruct *) IritMalloc(sizeof(EdgeStruct));
  677.     (*PEdgeNew2) -> Pnext = NULL;
  678.     (*PEdgeNew2) -> Internal = PEdge2 -> Internal;
  679.     (*PEdgeNew2) ->    Vertex[0] = IPAllocVertex(0, 0, NULL, NULL);
  680.     for (i = 0; i < 2; i++)
  681.         (*PEdgeNew2) -> Vertex[0] -> Coord[i] =
  682.         Crd20[i] * (1.0    - t2) +    Crd21[i] * t2;
  683.     (*PEdgeNew2) -> Vertex[0] -> Coord[2] = Z2;
  684.     /* Now update the second vertex    of both    PEdge2 & PEdgeNew2: */
  685.     (*PEdgeNew2) ->    Vertex[1] = PEdge2 -> Vertex[1];
  686.     PEdge2 -> Vertex[1] = (*PEdgeNew2) -> Vertex[0];
  687.     }
  688.     else
  689.     *PEdgeNew2 = NULL;
  690.  
  691.     return (*PEdgeNew1 != NULL) || (*PEdgeNew2 != NULL);
  692. }
  693.  
  694. /*****************************************************************************
  695. * Routine to print the content of a given edge:                     *
  696. *****************************************************************************/
  697. static void PrintPolyContent(IPPolygonStruct *PPoly)
  698. {
  699.     IPVertexStruct
  700.     *PList = PPoly -> PVertex;
  701.  
  702.     while (PList) {
  703.     fprintf(stderr, "   %12f %12f %12f\n",
  704.         PList -> Coord[0],
  705.         PList -> Coord[1],
  706.         PList -> Coord[2]);
  707.     PList =    PList -> Pnext;
  708.     }
  709. }
  710.  
  711. #ifdef DEBUG1
  712.  
  713. /*****************************************************************************
  714. * Routine to print the content of a given edge:                     *
  715. *****************************************************************************/
  716. static void PrintEdgeContent(EdgeStruct *PEdge)
  717. {
  718.     fprintf(stderr, "   %11f %11f %11f : %11f %11f %11f\n",
  719.     PEdge -> Vertex[0] -> Coord[0],
  720.     PEdge -> Vertex[0] -> Coord[1],
  721.     PEdge -> Vertex[0] -> Coord[2],
  722.     PEdge -> Vertex[1] -> Coord[0],
  723.     PEdge -> Vertex[1] -> Coord[1],
  724.     PEdge -> Vertex[1] -> Coord[2]);
  725. }
  726.  
  727. /*****************************************************************************
  728. * Routine to draw all the segments in the EdgeHashTable:             *
  729. *****************************************************************************/
  730. static void DrawEdgeHashTable(void)
  731. {
  732.     int    i;
  733.     EdgeStruct *PEtemp;
  734.  
  735.     for    (i=0; i<EDGE_HASH_TABLE_SIZE; i++) {
  736.     PEtemp = EdgeHashTable[i];
  737.     while(PEtemp) {
  738.         DrawEdge(PEtemp);
  739.         PEtemp = PEtemp -> Pnext;
  740.     }
  741.     }
  742. }
  743.  
  744. /*****************************************************************************
  745. * Routine to draw an edge:                             *
  746. *****************************************************************************/
  747. static void DrawEdge(EdgeStruct *PEdge)
  748. {
  749.     printf("    [POINTLIST 2\n\t[%lf %lf %lf]\n\t[%lf %lf %lf]\n    ]\n",
  750.        PEdge->Vertex[0]->Coord[0],
  751.        PEdge->Vertex[0]->Coord[1],
  752.        PEdge->Vertex[0]->Coord[2],
  753.        PEdge->Vertex[1]->Coord[0],
  754.        PEdge->Vertex[1]->Coord[1],
  755.        PEdge->Vertex[1]->Coord[2]);
  756.     printf("    [POLYLINE 2\n\t[%lf %lf %lf]\n\t[%lf %lf %lf]\n    ]\n",
  757.        PEdge->Vertex[0]->Coord[0],
  758.        PEdge->Vertex[0]->Coord[1],
  759.        PEdge->Vertex[0]->Coord[2],
  760.        PEdge->Vertex[1]->Coord[0],
  761.        PEdge->Vertex[1]->Coord[1],
  762.        PEdge->Vertex[1]->Coord[2]);
  763. }
  764.  
  765. #endif /* DEBUG1 */
  766.